package leetcode.code0402;

import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public String removeKdigits(String num, int k) {
		StringBuffer sb = new StringBuffer();
		Stack<Integer> stack = new Stack<>();
		char[] cs = num.toCharArray();
		int i = 0;
		for (; i < cs.length && k > 0; i++) {
			char cur = cs[i];
			while (!stack.isEmpty() && cs[stack.peek()] > cur && k > 0) {
				stack.pop();
				k--;
			}
			if (!stack.isEmpty() || (stack.isEmpty() && cur != '0')) {
				stack.add(i);
			}
		}
		while (k > 0 && !stack.isEmpty()) {
			stack.pop();
			k--;
		}
		while (!stack.isEmpty()) {
			sb.insert(0, cs[stack.pop()]);
		}
		for (int j = i; j < cs.length; j++) {
			if (sb.length() == 0 && cs[j] == '0') {
				continue;
			}
			sb.append(cs[j]);
		}
		if (sb.length() == 0) {
			return "0";
		}
		return sb.toString();
	}

	@Override
	public void debug4() {
		HelpDebug.compare("11", this.removeKdigits("112", 1));
		HelpDebug.compare("0", this.removeKdigits("9", 1));
		HelpDebug.compare("0", this.removeKdigits("10", 2));
		HelpDebug.compare("0", this.removeKdigits("102000000", 2));
		HelpDebug.compare("1219", this.removeKdigits("1432219", 3));
		HelpDebug.compare("200", this.removeKdigits("10200", 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
